# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.val)


class Solution:
    def postorderTraversal(self, root: TreeNode):
        result = []
        heap = [root]
        heapStatus = [0]
        if root is None:
            return result
        while len(heap):
            if heapStatus[-1] == 0:
                tmp = heap[-1]
                if tmp.left is None:
                    heapStatus[-1] = 1
                else:
                    heapStatus[-1] = 1
                    heapStatus.append(0)
                    heap.append(tmp.left)
            elif heapStatus[-1] == 1:
                tmp = heap[-1]
                if tmp.right is None:
                    heapStatus[-1] = 2
                else:
                    heapStatus[-1] = 2
                    heapStatus.append(0)
                    heap.append(tmp.right)
            else:
                tmp = heap.pop(-1)
                heapStatus.pop(-1)
                result.append(tmp.val)

        return result


if __name__ == '__main__':
    so = Solution()
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.left = TreeNode(3)
    result = so.postorderTraversal(root)
    print(result)
